1300. 转变数组后最接近目标值的数组和

给你一个整数数组arr和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。

如果有多种使得和最接近target 的方案，请你返回这些整数中的最小值。

请注意，答案不一定是arr中的数字。

示例 1：

输入：arr = [4,9,3], target = 10
输出：3
解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。

示例 2：

输入：arr = [2,3,5], target = 10
输出：5

示例 3：

输入：arr = [60864,25176,27249,21296,20204], target = 56803
输出：11361

提示：

1 <= arr.length <= 10^4
1 <= arr[i], target <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target

整理题目信息：

转换规则：arr数组中大于选取的value的元素均转换为value
要求找到使『转换后数组』的和与target相差最小的value
value可能不在arr数组中

思路及分析

需要找的value虽然可能不在arr数组内，但是必定在这个区间内[0, max(arr)]，在一个区间内快速寻找一位元素，可以使用『二分查找』

我们决定使用二分查找，那么二分的条件是什么？
按照题目要求的硬性条件，找到使『转换后数组』的和与target相差最小的value

结合上面的分析，这个条件转换一下就是让我们在[min(arr), max(arr)]区间内找一个value值，使其『转换后的数组』的和与target相差最小

『转换后的数组』的和后文均称为sum

在介绍二分的条件前，先说明下value值如何影响sum的大小
看图比较直观，value线以下的蓝色柱子部分相加就是sum，也就是说，value大则sum大，value小则sum小

再来具体看下二分的条件，分为以下三种情况：

首先说明 left = 0; right = max(arr)

如果sum小于target
注意：这里查找的是sum首次大于或等于target的情况
说明value过小，需要sum变大，则要让value值变大
所以下一次查找区间在[value+1, right]，即left = value + 1
如果sum大于target
说明value过大，需要sum变小，则要让value值变小
所以下一次查找区间在[left, value]，即right = value
如果sum等于target
我们需要的是使sum首次大于或等于target的value
所以下一次查找区间在[left, value]，即right = value

二分查找结束! 找到了什么？找到的value使sum第一次大于或等于target

题目要求sum与target最接近，此时
value使sum第一次大于或等于target，可能是最接近的
value-1使sum最后一次小于target，也有可能是最接近的
所以这俩再比较比较，与target相差小的sum其对应的value就是答案了

代码实现

二分查找的范围

left, right = 0, max(arr)

二分查找value值

注: calculate_sum求和函数

while left < right:
    value = (left + right) >> 1
    # 当前value求出的和
    sum = calculate(arr, value)
    if sum < target:
        left = value + 1
    else:
        right = value

求和函数

求和规则：使得将数组中所有大于value 的值变成 value 后，求转换后数组的和

def calculate_sum(arr, value):
    ans = 0
    for num in arr:
        ans += min(num, value)
    return num

最后的比较

sum1 = calculate(arr, left-1)
sum2 = calculate(arr, left)
if target - sum1 <= sum2 - target:
    return left-1
return left

完整代码

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        left, right = 0, max(arr)
        while left < right:
            mid = (left + right) >> 1
            sum = self.calculate_sum(arr, mid)
            if sum < target:
                left = mid + 1
            else:
                right = mid
        sum1: int = self.calculate_sum(arr, left-1)
        sum2: int = self.calculate_sum(arr, left)
        if target - sum1 <= sum2 - target:
            return left - 1
        return left

    def calculate_sum(self, arr: List[int], mid: int) -> int:
        ans: int = 0
        for num in arr:
            ans += min(num, mid)
        return ans

解法二

先对arr数组进行升序排序，此时arr数组可以看做两部分：

小于arr的和为sum，那么大于或等于value的部分总和为target-sum

根据转换规则，大于value的元素都转为等于value，再依赖排序后的单调性，target-sum / 大于或等于value的元素个数，就可以求得大于value的元素的平均数avg

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        s,n=0,len(arr)
        for i in range(len(arr)):
            avg=(target-s)/(n-i)
            if avg<arr[i]:
                return int(avg+0.4999999)   #五舍六入
            s+=arr[i]
        return arr[-1]